package lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 17:10
 * description:单链表中的哨兵节点
 */
public class SentinelSinglyLinkedList {
    // 链表节点内部类
    static class Node {
        Integer data;  // 数据域
        Node next;     // 指向下一个节点的引用

        // 无参构造（用于创建哨兵节点，data为null）
        public Node() {
            this.data = null;
            this.next = null;
        }

        // 有参构造（用于创建实际数据节点）
        public Node(Integer data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node sentinel;  // 哨兵节点（固定存在，不存储实际数据）

    // 单哨兵单向链表构造方法（初始化哨兵节点）
    public SentinelSinglyLinkedList() {
        this.sentinel = new Node();  // 哨兵节点data默认null，next默认null
        this.sentinel.next = null;
    }

    /**
     * 检查链表是否为空（实际节点为空）
     * @return 空返回true，非空返回false
     */
    public boolean isEmpty() {
        return sentinel.next == null;
    }

    /**
     * 在链表头部插入节点（哨兵节点之后）
     * @param data 插入的节点数据
     */
    public void prepend(Integer data) {
        Node newNode = new Node(data);
        // 新节点指向哨兵节点的原后继
        newNode.next = sentinel.next;
        // 哨兵节点指向新节点，完成头插
        sentinel.next = newNode;
    }

    /**
     * 在链表尾部插入节点
     * @param data 插入的节点数据
     */
    public void append(Integer data) {
        Node newNode = new Node(data);
        Node current = sentinel;

        // 遍历到最后一个实际节点（current.next为null时停止）
        while (current.next != null) {
            current = current.next;
        }

        // 最后一个节点指向新节点
        current.next = newNode;
    }

    /**
     * 删除第一个实际节点（哨兵节点的后继）
     * @return 删除成功返回true，空链表返回false
     */
    public boolean deleteFirst() {
        if (isEmpty()) {
            return false;
        }

        // 哨兵节点跳过第一个实际节点，直接指向其下一个
        sentinel.next = sentinel.next.next;
        return true;
    }

    /**
     * 删除指定数据的实际节点
     * @param data 要删除的节点数据
     * @return 删除成功返回true，未找到/空链表返回false
     */
    public boolean delete(Integer data) {
        if (isEmpty()) {
            return false;
        }

        Node prev = sentinel;       // 前驱节点（从哨兵开始）
        Node current = sentinel.next;  // 当前节点（第一个实际节点）

        while (current != null) {
            // 匹配数据时，前驱节点跳过当前节点
            if (current.data.equals(data)) {
                prev.next = current.next;
                return true;
            }
            prev = current;
            current = current.next;
        }

        return false;  // 遍历结束未找到目标节点
    }

    /**
     * 遍历链表，返回所有实际节点的数据
     * @return 存储节点数据的List集合
     */
    public List<Integer> traverse() {
        List<Integer> result = new ArrayList<>();
        Node current = sentinel.next;  // 从第一个实际节点开始遍历

        while (current != null) {
            result.add(current.data);
            current = current.next;
        }

        return result;
    }

    public static void main(String[] args) {
        // 1. 创建单哨兵单向链表实例
        SentinelSinglyLinkedList sll = new SentinelSinglyLinkedList();

        // 2. 初始链表为空检查
        System.out.println("初始链表是否为空: " + sll.isEmpty());  // 输出: true

        // 3. 头部插入元素（10, 20, 30）
        sll.prepend(30);
        sll.prepend(20);
        sll.prepend(10);
        System.out.println("头部插入10, 20, 30后链表内容: " + sll.traverse());  // 输出: [10, 20, 30]

        // 4. 尾部插入元素（40, 50）
        sll.append(40);
        sll.append(50);
        System.out.println("尾部插入40, 50后链表内容: " + sll.traverse());  // 输出: [10, 20, 30, 40, 50]

        // 5. 删除第一个节点
        sll.deleteFirst();
        System.out.println("删除第一个节点后链表内容: " + sll.traverse());  // 输出: [20, 30, 40, 50]

        // 6. 删除指定值节点（存在：30）
        sll.delete(30);
        System.out.println("删除值为30的节点后链表内容: " + sll.traverse());  // 输出: [20, 40, 50]

        // 7. 删除指定值节点（不存在：60）
        boolean success = sll.delete(60);
        System.out.println("尝试删除值为60的节点是否成功: " + success);  // 输出: false

        // 8. 再次检查链表是否为空
        System.out.println("链表是否为空: " + sll.isEmpty());  // 输出: false

        // 9. 清空链表（删除所有实际节点）
        sll.deleteFirst();
        sll.deleteFirst();
        sll.deleteFirst();
        System.out.println("清空链表后链表内容: " + sll.traverse());  // 输出: []
        System.out.println("清空后链表是否为空: " + sll.isEmpty());  // 输出: true

        // 10. 对空链表执行删除第一个节点操作
        success = sll.deleteFirst();
        System.out.println("对空链表删除第一个节点是否成功: " + success);  // 输出: false
    }
}